package 经典排序;

import com.alibaba.fastjson.JSON;

import java.util.*;

public class No215数组中第K大的元素 {

    Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        // 要找到的元素所在索引:  前K大，即倒数索引第K个
        int index = nums.length - k;
        int right = nums.length - 1;
        int left = 0;
        return quickSelect(nums, left, right, index);
    }

    public int quickSelect(int[] nums, int left, int right, int index) {
        // 得到分区值索引q
        int q = randomPartition(nums, left, right);

        if (q == index) {
            // 如果刚好索引q就是想要的索引，则直接返回
            return nums[q];

        } else {
            // 如果不是，比较q 与 index ,确定下次要检索的区间, 要么是[q+1, right], 要么就是[left, q-1]
            return q < index ? quickSelect(nums, q + 1, right, index) : quickSelect(nums, left, q - 1, index);
        }
    }

    public int randomPartition(int[] nums, int l, int r) {
        // 1. 随机数范围: [0, r-l+1) 同时加l, 则是 [l, r+1) = [l, r] 也就是在这个[l,r] 中随机选一个索引出来
        /**
         * 随机找一个随机元素来当右边界,为什么?那继续看下面的方法
         * 虽然会找到一样的随机数,但是以这个随机数为索引取到的值却是不同的
         */
        int i = random.nextInt(r - l + 1) + l;

        // 2. 交换nums[i]， nums[r], 也就是将随机数先放在[l,r]最右边nums[r]上
        swap(nums, i, r);
        /**
         * 右边界还是最右没有变,只有右边界的那个值变了,整条链路l,r都没变
         * 这个随机数就是来挑,挑第N大的数看运气好不好
         */
        return partition(nums, l, r);
    }

    public int partition(int[] nums, int l, int r) {
        /**
         * x就是传进来的右边界是上一个方法随机挑选的一个元素
         */
        // 3. 在调用当前方法的randomPartition方法中，已经确定了了随机数是nums[r]
        int x = nums[r], i = l - 1;

        // 首先比较区间在[l， r]之间， 所以nums[j]中的    l<= j <= r
        for (int j = l; j < r; ++j) {
            // 4. nums[j] 跟随机数 x 比较, 小于x的数都跟[l,r]左边区间交换，i=l-1,所以++i=l,初始索引就是l,
            if (nums[j] <= x) {
                swap(nums, ++i, j);//两两交换
            }
        }// 这个for循环操作就是将小于 x 的数都往[i, j]的左边区间设置，从而实现存在[l, i]区间,使得对应数值都 小于 x

        //5. 既然已经将<x的值都放在一边了，现在将x也就是nums[r] 跟nums[i+1]交换，
        //从而分成两个区间[l.i+1]左, [i+2, r]右，左边区间的值都小于x
        swap(nums, i + 1, r);
        /**
         * 有了i,i这个索引上的值就是以x划分的大小线,将x放到中间,确保两边是一个都小于,一个都大于
         */

        // 然后返回这个分区值
        return i + 1;
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    static class MaxHeap{
        //我感觉上面那个解法很随机,所以我还是想用比较稳定的堆排序
        /**
         * 记住了,堆不是二分搜索树,并且最后一个下标对应的也不是最小的元素,所以我们要依次取出才知道第k大的元素!
         */

        /**
         * 坐标寻找方法,公式要记住
         */
        private int parent(int index){
            return (index-1)/2;
        }

        private int leftChild(int index){
            return index*2+1;
        }

        private int rightChild(int index){
            return index*2+2;
        }

        /**
         * 以数组作为最大堆的体现
         */
        private int[] arr;
        private int currentIndex;//记录元素个数

        public MaxHeap(int capacity){
            arr=new int[capacity];
        }

        public void add(int a){

            /**
             * 不能这么做,因为最后一个不一定是最小的
             */
//            if(currentIndex==arr.length-1){
//                //已经满了,就和最后一个比较
//                if(a<=arr[currentIndex])
//                    return;
//            }

            //加到最后面
            arr[currentIndex]=a;
            //然后维护整个堆
            siftUp(currentIndex);
            if(currentIndex!=arr.length-1)//最大了
                currentIndex++;
        }

        private void siftUp(int k){//使一个数组下标的元素上浮

            while (k>0&& arr[parent(k)]<arr[k] ){//父节点比当前节点小的情况
                //避免出现新添加元素大于父节点,而打破规则的情况

                swap(k,parent(k));//交换即可

                k=parent(k);//记得更改k的值,因为还要继续向上寻找

            }
        }

        private void swap(int oneIndex,int twoIndex){
            int op=arr[oneIndex];
            arr[oneIndex]=arr[twoIndex];
            arr[twoIndex]=op;
        }

        private int getMax(){

            int max=arr[0];
            arr[0]=arr[currentIndex];
            arr[currentIndex]=0;//去除末尾
            currentIndex--;
            siftDown(0);//下沉
            return max;

        }

        //下沉操作,取出后max头后,将最末尾的拉到头上,然后去除末尾,让头开始下沉
        private void siftDown(int k){

            //比较左右节点,谁大就去和谁换
            //注意点,不能过界,就是当前节点的左节点存在
            while(leftChild(k)<arr.length){
                //和谁换?
                int index=leftChild(k);

                if(rightChild(k)<arr.length&&arr[rightChild(k)]>arr[leftChild(k)])
                    index++;//去和右节点换

                if(arr[k]>arr[index]){
                    //都大于它的两个子节点了,就break出去,替换完毕
                    break;
                }
                swap(index,k);
                k=index;
            }

        }



    }

    public static void main(String[] args) {

        int[] arr=new int[]{3,-3,2,1,5,6,4,-2};
        No215数组中第K大的元素.MaxHeap n=new No215数组中第K大的元素.MaxHeap(6);
        for(int i=0;i<arr.length;i++)
            n.add(arr[i]);

        for(int i=0;i<2;i++)
            System.out.println(n.getMax());

    }

}
